/**
 * @file xcd_util.c
 * @brief Collection of useful utility functions.
 * @author Guo-Rong Koh
 * @date 25 February 2008
 *
 * @par Copyright Notice
 * Copyright Guo-Rong Koh 2008.
 */

/*
 * This file is part of xceed.
 *
 * xceed is free software: you can redistribute it and/or modify it under the
 * terms of the GNU General Public License Version 2 as published by the Free
 * Software Foundation.
 *
 * xceed is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
 * A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along with
 * xceed.  If not, see <http://www.gnu.org/licenses/>.
 */

#include "xcd_util.h"

unsigned int xcd_util_popcount32(register unsigned int x)
{
    /*
     * Implementation borrowed from:
     * http://aggregate.org/MAGIC/#Population Count (Ones Count)
     */

    /* 32-bit recursive reduction using SWAR...  but first step is mapping 2-bit
     * values into sum of 2 1-bit values in sneaky way.
     */
    x -= ((x >> 1) & 0x55555555);
    x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
    x = (((x >> 4) + x) & 0x0f0f0f0f);
    x += (x >> 8);
    x += (x >> 16);
    return(x & 0x0000003f);
}
